# coding:utf-8
'''
    冒泡排序:每次相邻的两个元素比较(每次把剩余中最大/小)的放到右边)
    时间复杂度: 最优:O(n)   最坏:O(n²)
    稳定性:稳定
'''


def bubble_sort(list):
    '''冒泡排序'''
    n = len(list)
    for i in range(n - 1):
        count = 0  # 用来判断是否是最优(数组本身是有序的)
        for j in range(n - 1 - i):  # 下标减1
            if list[j] > list[j + 1]:
                count += 1
                list[j], list[j + 1] = list[j + 1], list[j]
        if count == 0:
            return


if __name__ == "__main__":
    list = [23, 43, 1, 245, 97, 4546, 212]
    bubble_sort(list)
    print(list)
